/*
    ax + by = 1一组整数值
    ax + by = gcd(a, b) 恒等于1
*/
#include <stdio.h>
int ex_gcd(int a, int b, int *x, int *y)
{
    if(!b){
        *x = 1, *y = 0; // y为任意值
        return a;
    }
    /*
    int xx, yy, ret = ex_gcd(b, a % b, &xx, &yy);
    *x = yy;
    *y = xx - a / b * yy;
    */
    int ret = ex_gcd(b, a % b, y, x);
    *y -= a / b * (*x);
    return ret;
}
int main(int argc, char *argv[])
{
    int a, b, x, y;
    while(~scanf("%d %d", &a, &b))
    {
        if(a == 0 && b == 0) break;
        printf("ex_gcd(%d, %d) = %d\n", a, b, ex_gcd(a, b, &x, &y));
        printf("%d * %d + %d * %d = %d\n", a, x, b, y, a * x + b * y);
    }
    return 0;
}